/**
 * 闭散列Hash表
*/
#pragma once
#include <iostream>
#include <vector>
#define close_hash 0
#if close_hash

    enum State
    {
        Empty,
        Exist,
        Delete
    };

    template <class K>
    struct hashnode
    {
    public:
        hashnode()
            : _state(Empty), _data(std::make_pair<K, int>(K(), 0))
        {
        }

    public:
        State _state;            // 表示当前位置的状态
        std::pair<K, int> _data; // K存元素值，V存出现次数
    };

    template <class K>
    class hash
    {
        using Node = hashnode<K>;

    public:
        hash(const size_t capa = 3)
            : _hashlist(new std::vector<Node>(capa, Node())), _capa(capa), _size(0)
        {
        }

        ~hash()
        {
            delete _hashlist;
        }

        void insert(const K &value)
        {
            CheckCapacity(); // 判断是否需要扩容

            int pos = hashfun(value);
            // int i = 1;
            while (pos < _capa && _hashlist->at(pos)._state == Exist && _hashlist->at(pos)._data.first != value)
            {
                ++pos; // 线性探测
                // pos = (pos + i ^ 2) % _capa; // 二次探测
                if (pos >= _capa)
                    pos = 0;
                // ++i;
            }

            _hashlist->at(pos)._data.first = value;
            ++_hashlist->at(pos)._data.second;
            _hashlist->at(pos)._state = Exist;
            ++_size;
        }

        void erase(const K &value)
        {
            int pos = find(value);
            if (pos != -1)
            {
                if (--_hashlist->at(pos)._data.second == 0)
                    _hashlist->at(pos)._state = Delete;
                --_size;
            }
        }

        size_t find(const K &value)
        {
            int pos = hashfun(value);
            int fpos = pos;
            int flag = 0;
            while (pos < _capa && _hashlist->at(pos)._state != Empty)
            {
                if (_hashlist->at(pos)._state == Exist && _hashlist->at(pos)._data.first == value)
                    return pos;
                ++pos;

                if (pos == _capa)
                {
                    pos = 0;
                    flag = 1;
                }

                if (pos == fpos && flag == 1) // 已经轮了一圈
                {
                    break;
                }
            }
            return -1;
        }

        size_t size() { return _size; }
        size_t capacity() { return _capa; }
        bool empty() { return _size == 0; }

    private:
        size_t hashfun(const K &value)
        {
            return value % _capa;
        }

        void CheckCapacity()
        {
            if (_size * 10 / _capa >= 7)
            {
                hash<K> *new_hashlist = new hash<K>(_capa * 2);

                for (int i = 0; i < _hashlist->size(); ++i)
                {
                    new_hashlist->insert(_hashlist->at(i)._data.first);
                }

                delete _hashlist;

                _hashlist = new_hashlist->_hashlist;
                _capa = new_hashlist->_capa;
                _size = new_hashlist->_size;
            }
        }

    private:
        std::vector<Node> *_hashlist;
        size_t _capa; // 容量
        size_t _size; // 个数
    };

#else 




    template <class T>
    struct hashnode
    {
        hashnode(const T& data = T())
            : _data(data)
            , _next(nullptr)
        {}

        T _data;
        hashnode<T>* _next;
    };

    template <class T>
    class hash
    {
    public:
        using Node = hashnode<T>;
    public:
        hash(const size_t capa = 3)
            : _hash_table(capa, new Node())
            , _capa(capa)
            , _size(0)
        {}
        ~hash()
        {
            for(int i = 0; i < _hash_table.size(); ++i)
            {
                Node* cur = _hash_table[i];
                while(cur != nullptr)
                {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
            }
        }
        void insert(const T& data)
        {
            CheckCapacity(); // 判断是否需要扩容

            int hash_addr = hashFun(data);
            Node* cur = _hash_table[hash_addr];
            while(cur->_next != nullptr)
            {
                cur = cur->_next;
            }

            Node* newnode = new Node(data);
            cur->_next = newnode;
            ++_size;
        }
        void erase(const T& data)
        {
            size_t hash_addr = find(data);
            if(hash_addr != -1)
            {
                Node* cur = _hash_table[hash_addr];
                Node* next = cur->_next;
                while(next->_data != data)
                {
                    cur = cur->_next;
                    next = next->_next;
                }
                cur->_next = next->_next;
                delete next;
                next = nullptr;
                --_size;
            }
        }
        size_t find(const T& data)
        {
            int hash_addr = hashFun(data);
            Node* cur = _hash_table[hash_addr]->_next;
            while(cur != nullptr)
            {
                if(cur->_data = data)
                    return hash_addr;
                cur = cur->_next;
            }
            return -1;
        }
        size_t size() {return _size;}
        size_t capacity() {return _capa;}
        bool empty() {return _size == 0;}
    private:
        size_t hashFun(const T& data)
        {
            return data % _capa;
        }
        void CheckCapacity()
        {

        }
    private:
        std::vector<Node*> _hash_table;
        size_t _capa;
        size_t _size;
    };
    
#endif
